#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int numDecodings(string s) {
    int dp[110] = { 0 };
    int n = s.size();
    dp[0] = 1;
    if (s[0] != '0')
        dp[1] = 1;
    if (n == 1)
        return dp[1];

    for (int i = 2; i <= n; ++i)
    {
        if (s[i - 1] != '0')
            dp[i] += dp[i - 1];
        int t = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
        if (t >= 10 && t <= 26)
            dp[i] += dp[i - 2];
    }

    return dp[n];
}


int main()
{
    numDecodings("12");
	return 0;
}